package LC;

import java.util.ArrayList;
import java.util.List;

public class Lc46 {
    public static void main(String[] args) {
        new Lc46().permute(new int[]{1, 2, 3});
    }

    private final List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        traceBack(nums, 0, new ArrayList<>());
        return ans;
    }

    public void traceBack(int[] nums, int index, List<Integer> temp) {
        if (temp.size() == nums.length) {
            ans.add(new ArrayList(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!temp.contains(nums[i])) {
                temp.add(nums[i]);
                traceBack(nums, i, temp);
                temp.remove(temp.size() - 1);
            }
        }
    }
}
